package leetcode_901_1000;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeeCode_952 {
    public static void main(String[] args) {
        System.out.println(largestComponentSize(new int[]{4, 6, 15, 35}));
        System.out.println(largestComponentSize(new int[]{20, 50, 9 ,63}));
    }
    private static int largestComponentSize(int[] nums){
        int[] p = new int[nums.length];
        for (int i = 0; i < p.length; i++) {
            p[i] = i;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            getAll(map, nums[i], i);
        }
        for (Integer key : map.keySet()) {
            List<Integer> list1 = map.get(key);
            for (int i = 0; i < list1.size() - 1; i++) {
                union(p, list1.get(i), list1.get(i + 1));
            }
        }
        Map<Integer, Integer> m2 = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int r = find(p, i);
            m2.put(r, m2.getOrDefault(r, 0) + 1);
        }
        int ans = 0;
        for (Integer key : m2.keySet()) {
            ans = Math.max(ans, m2.get(key));
        }
        return ans;
    }
    private static void getAll(Map<Integer, List<Integer>> map, int n, int i){
        if (isZhi(n)){
            if (map.containsKey(n)){
                map.get(n).add(i);
            }else {
                List<Integer> son = new ArrayList<>();
                son.add(i);
                map.put(n, son);
            }
            return;
        }
        int k = 2;
        while (k * k <= n){
            if (n % k == 0 && isZhi(k)){
                if (map.containsKey(k)){
                    map.get(k).add(i);
                }else {
                    List<Integer> son = new ArrayList<>();
                    son.add(i);
                    map.put(k, son);
                }
                if (k != n / k){
                    getAll(map, n / k, i);
                }
            }
            k++;
        }
    }
    private static int find(int[] p, int x){
        if (p[x] != x){
            p[x] = find(p, p[x]);
        }
        return p[x];
    }
    private static void union(int[] p, int x, int y){
        int rx = find(p,x);
        int ry = find(p,y);
        p[rx] = p[ry];
    }
    private static boolean isZhi(int n){
        int i = 2;
        while (i * i <= n){
            if (n % i == 0){
                return false;
            }
            i++;
        }
        return true;
    }

}
